package com.rr.middle;

import com.rr.entity.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author RR
 * @date 2022/10/15 22:40
 */
/*
* https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/
* 个人解法有点笨，遍历一遍获得所有结点，再重新构建树，题目原意应该是想展开树
* */
public class FlattenBinaryTreeToLinkedList {
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        List<TreeNode> list = new ArrayList<>();
        fillList(list, root);
        System.out.println(list.size());
        root.left = null;
        root.right = null;
        TreeNode tmp = root;
        for (TreeNode treeNode : list) {
            tmp.right = treeNode;
            tmp = tmp.right;
            treeNode.left = null;
            treeNode.right = null;
        }
        System.out.println(root);
    }

    private void fillList(List<TreeNode> list, TreeNode root) {
        if (root.left != null) {
            list.add(root.left);
            fillList(list, root.left);
        }
        if (root.right != null) {
            list.add(root.right);
            fillList(list, root.right);
        }
    }


    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1);
        treeNode.left = new TreeNode(2);
        treeNode.right = new TreeNode(5);
        treeNode.left.left = new TreeNode(3);
        treeNode.left.right = new TreeNode(4);
        treeNode.right.right = new TreeNode(6);
        new FlattenBinaryTreeToLinkedList().flatten(treeNode);
    }
}
